package middle;

import java.util.LinkedList;
import java.util.Stack;

public class Solution_98 {

    public boolean isValidBST(TreeNode root) {
        LinkedList<Long> maxes = new LinkedList<>();
        LinkedList<Long> mines = new LinkedList<>();
        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        maxes.add(Long.MAX_VALUE);
        mines.add(Long.MIN_VALUE);
        while (!nodes.isEmpty()) {
            TreeNode poll = nodes.poll();
            Long max = maxes.poll();
            Long min = mines.poll();
            if (poll.val > min && poll.val < max) {
                if (poll.left != null) {
                    nodes.add(poll.left);
                    maxes.add((long) poll.val);
                    mines.add(min);
                }
                if (poll.right != null) {
                    nodes.add(poll.right);
                    mines.add((long) poll.val);
                    maxes.add(max);
                }
            } else {
                System.out.println(poll.val);
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution_98 model = new Solution_98();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(6);
        System.out.println(model.isValidBST(root));
    }

    static class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
